package leetcode_day._2021._202109._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/10 8:57
 * 找到需要补充粉笔的学生编号
 * 算法：数组  前缀和  二分查找
 */
public class _10_1894 {
    public static void main(String[] args) {
        int[] chalk = {3, 4, 1, 2};
        int k = 25;
        System.out.println(new _10_1894().chalkReplacer(chalk, k));
    }

    public int chalkReplacer(int[] chalk, int k) {
        if (chalk[0] > k) return 0;
        int n = chalk.length;
        long[] pre = new long[n];
        pre[0] = chalk[0];
        for (int i = 1; i < n; i++) {
            pre[i] = chalk[i] + pre[i - 1];
            if (pre[i] > k) return i;
        }
        long tmp = k % pre[n - 1];
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (tmp < pre[mid]) r = mid;
            else l = mid + 1;
        }
        return l;
    }

}
